/* 
 * File:   ArbolB.h
 * Author: jesus
 *
 * Created on 15 de junio de 2010, 12:54
 */

#ifndef _ARBOLB_H
#define	_ARBOLB_H
#include <map>
#include <iostream>
using namespace std;
        
template<class ClaveP,unsigned orden>
class NodoArbolB{
    struct Indice{ClaveP clave;unsigned long posicion;};

    Indice indices[orden];
    unsigned int ocupacion;
    bool hoja;
    

public:
    NodoArbolB(){ocupacion=0; hoja=true;}
    NodoArbolB(NodoArbolB &cop);
    ~NodoArbolB();
    void insertar(ClaveP &clave,unsigned long posicion);
    void eliminar(ClaveP &clave);
    ClaveP claveMenor();
    bool esHoja(){return hoja;}
    bool estaLleno(){return ocupacion==orden;}
    unsigned long buscar(ClaveP clave);
    void dividir(NodoArbolB &nodoDest);

};

   

    NodoArbolB::NodoArbolB(NodoArbolB &cop){

    }
    NodoArbolB::~NodoArbolB(){

    }
    void NodoArbolB::insertar(ClaveP &clave,unsigned long posicion){

        if(ocupacion<orden){
            int i=0;
            //Busca la posicion donde se inserta el elemento
            while(indices[i].clave<clave){ i++; }

            //desplaza los elementos para insertar posteriormente el dato
            for(int j=ocupacion-1;j>i;j--){
                indices[j]=indices[j-1];
            }

            //Insercion del dato
            indices[i].clave=clave;
            indices[i].posicion=posicion;
            ocupacion++;
        }
    }
    void NodoArbolB::eliminar(ClaveP &clave){
        if(ocupacion){
            int i=0;
            //Busca la posicion donde se inserta el elemento
            while(indices[i].clave<clave){ i++; }
            ocupacion--;

            //desplaza los elementos para insertar posteriormente el dato
            for(int j=1;j<ocupacion;j++){
                indices[j]=indices[j+1];
            }

        }
        //else throw NODOVACIO;
    }
    ClaveP NodoArbolB::claveMenor(){
        ClaveP menor=indices[0].clave;

        for(int i=0;i<ocupacion;i++){
            if(menor<=indices[i].clave){
                menor=indices[i].clave;
            }
        }
       return menor;
    }
    unsigned long NodoArbolB::buscar(ClaveP clave){
        unsigned long busc;
        if(esHoja()){
            int i=0;
            while(indices[i].clave!= clave && i<ocupacion){i++;}
            if(indices[i].clave==clave){busc=indices[i].posicion;}
            else busc=1;
        }
        else{
            int j=0;
            while(clave>indices[j] && j<ocupacion){j++;}
            if(j==0){ busc=indices[j].posicion;}
            else{j--; busc=indices[j].posicion;}

        }
        return busc;
    }
    void NodoArbolB::dividir(NodoArbolB &nodoDest){

        if(ocupacion==orden){
            for(int i=ocupacion/2;i<ocupacion;i++){
                nodoDest.insertar(indices[i].clave,indices[i].posicion);
            }
        }
        
    }
#endif	/* _ARBOLB_H */

